package caip2025n.rcv4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/*
地点1, 地点2, A, B
A, 地点1(from), 地点2(to) 各自为起点跑一次最短路
注: (from, to)这条路免费 
得到可能的路径关系式
方案1.[A(起点)->B(终点)]
方案2.[A(起点)->from(终点)+to(起点)->B(终点)]-[(from,to)收费]
方案3.[A(起点)->to(终点)+from(起点)->B(终点)]-[(from,to)收费] 
三个关系式在存在通路的情况下取最小就是解
*/

public class Main {

	// 输入优化模板开始
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StreamTokenizer st = new StreamTokenizer(br);
	static int rd() throws IOException {
		st.nextToken();
		return (int) st.nval;
	}
	// 输入优化模板结束

	// 最大整数表示无通路
	static int INF = Integer.MAX_VALUE;
	// 图——邻接表
	static List<List<int[]>> g = new ArrayList<>();
	//快速查询两点间的边权
	static int[][] mp = new int[105][105];

	public static int[] dijkstra(int start) {
    	//两点间的路径长度
    	int[] dist = new int[n+1];
    	Arrays.fill(dist, INF);
    	//路径点分组
    	boolean[] visited = new boolean[n+1];
    	Arrays.fill(visited, false);
    	
        //优先队列([点id，路径长度])
    	PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				//该优先队列是小顶堆，大的往后放
				return o1[1] - o2[1];
			}
        });
        //放入起点
        pq.offer(new int[]{start,0});
        dist[start] = 0;
        while (!pq.isEmpty()) {
            //取出距离start最近的点
            int[] cur = pq.poll();
            int from = cur[0]; 
            
            //如果该顶点已访问过，跳过（防止重复处理）
            if (visited[from]) 
            	continue;
            
            visited[from] = true;
            //遍历from的每条边from-to，如果能通过from使得start到to的距离变得更短，更新start到to的距离dist[to]
            for(int i=0;i<g.get(from).size();i++) {
                int to = g.get(from).get(i)[0];
                int weight = g.get(from).get(i)[1];
                if (!visited[to] && dist[to] > dist[from] + weight) {
                    dist[to] = dist[from] + weight;
                    //将v加入优先队列，下次参与比较距离start最近的点
                    pq.offer(new int[] {to,dist[to]});
                }
            }
        }      
        return dist;
    }

	static int n;
	static int k;
	static int m;
	public static void main(String[] args) throws IOException {
		n = rd();
		m = rd();
		k = rd();

		// 创建点的列表
		// g = new ArrayList<>[n + 1];
		// 注意：点从1开始编号，但ArrayList需要从0开始依次添加实例
		for (int i = 0; i <= n; i++) {
			g.add(new ArrayList<>());
		}

		// 添加边
		// get(点id)，add(边(终点，权重))
		while (m > 0) {
			m--;
			int u = rd();
			int v = rd();
			int w = rd();
			//一条双向通路，添加两个边
			g.get(u).add(new int[] { v, w });
			g.get(v).add(new int[] { u, w });
			//快速查询两个点之间的边权
			mp[u][v] = w;
			mp[v][u] = w;
		}
		
		//获取询问，输出结果
		while(k>0) {
			k--;
			int from = rd();
			int to = rd();
			int A = rd();
			int B = rd();
			int[] D1 = dijkstra(A);
			int[] D2 = dijkstra(from);
			int[] D3 = dijkstra(to);
			
			long ans = INF;
			//方案1判断
			if(D1[B]<INF)
				ans = D1[B];
			//方案2判断
			if(D1[from]<INF && D3[B]<INF) {
				ans = Math.min(ans, D1[from]+D3[B]-mp[from][to]);
			}
			//方案3判断
			if(D1[to]<INF && D2[B]<INF) {
				ans = Math.min(ans, D1[to]+D2[B]-mp[from][to]);
			}
			
			//无通路
			if(ans>=INF) {
				System.out.println("@_@");
			}else {
				System.out.println(Math.max(0, ans));
			}		
		}
	}
}


